#85勾股数元组
# start = int(input())
# end = int(input())
# arr = [i*i for i in range(start,end+1)]
# print(arr)
# def isRelativePrime(a,b):
#     while b > 0:
#         mod = a % b
#         a = b
#         b = mod
#     return a == 1
# res = []
# for x in range(0,len(arr)):
#     for y in range(x+1,len(arr)):
#         if arr[x] + arr[y] in arr:
#             a = int(math.sqrt(arr[x]))
#             b = int(math.sqrt(arr[y]))
#             c = int(math.sqrt(arr[y]+arr[x]))
#             if isRelativePrime(b,a) and isRelativePrime(c,b) and isRelativePrime(c,a):
#                 res.append(f"{a} {b} {c}")
# print(res)


#86数组连续和
# n,x = map(int,input().split())
# arr = list(map(int,input().split()))
# length = len(arr)
# prefix = [0] * (length+1)
# for i in range(1,length+1):
#     prefix[i] = prefix[i-1] + arr[i-1]
#
# l = 0
# r = 0
# ans = 0
# while r <= n:
#     if prefix[r] - prefix[l] >= x:
#         ans += n-1-r+1
#         l+=1
#         r = l + 1
#     else:
#         r+=1

#87字符串摘要
# s = input()
# s = s.lower()
# count = {}
# letters = []
# for c in s:
#     if 'a' <= c <= 'z':
#         count[c] = count.get(c,0) + 1
#         letters.append(c)
# s = ''.join(letters) + " "
# count[' '] = 1
# pre = s[0]
# repeat = 1
# count[pre] -= 1
# ans = []
# for i in range(1,len(s)):
#     cur = s[i]
#     count[cur] -= 1
#     if cur == pre:
#         repeat+=1
#     else:
#         ans.append([pre,repeat if repeat > 1 else count[pre]])
#         pre = cur
#         repeat = 1
# print(ans)
# ans.sort(key = lambda  x: (-x[1],x[0]))
# print(''.join(map(lambda x: x[0] + str(x[1]),ans)))

#88用户调度
# n = int(input())
# Exidx = -1
# ret = 0
# minnum = sys.maxsize
# arr = [list(map(int,input().split())) for _ in range(n)]
# for j in range(3):
#     # print(Minidx)
#     for i in range(3):
#         if  i == Exidx:
#             continue
#         if arr[j][i] <= minnum:
#             minnum = arr[j][i]
#             Minidx = i
#     Exidx = Minidx
#     ret += arr[j][Minidx]
#     minnum = sys.maxsize
# print(ret)

#89数组去重后排序
# nums = list(map(int,input().split(',')))
# count = {}
# first = {}
# for i in range(len(nums)):
#     s = nums[i]
#     if count.get(s) is None:
#         count[s] = 0
#     count[s] += 1
#     # count[s] = count.get(s,0)+1
#     if first.get(s) is None:
#         first[s] = i
#
# tmp = list(first.keys())
# tmp.sort(key = lambda x:(-count[x],first[x]))
# # print(tmp)
# print(','.join(tmp))
# print(','.join(map(str,tmp)))

#90玩牌
# cards = list(map(int,input().split(',')))
# n = len(cards)
# dp = [0] * n
# dp[0] = max(0,cards[0])
# for i in range(1,n):
#     if i < 3:
#         dp[i] = max(dp[i-1]+cards[i],0)
#     else:
#         dp[i] = max(dp[i-1]+cards[i],dp[i-3])
# print(dp[n-1])

#91机房布局
# s = input
# n = len(s)
# i = 0
# ans = 0
# while i < n:
#     if s[i] == 'M':
#         if s[i+1] == 'I' and i+1 < n:
#             ans+=1
#             i+=2
#         elif s[i-1] == 'I' and i-1 >=0:
#             ans+=1
#         else:
#             ans = -1
#             break
#     i+=1

#92MVP争夺战
# m = int(input())
# link = list(map(int,input().split()))
#
# def getRes(link,m):
#     link.sort(reverse = True)
#     print(link)
#     sumV = 0
#     for num in link:
#         sumV+= num
#
#     while m >= 1:
#         if canPartition(link,sumV,m):
#             return sumV/m
#         m -= 1
#     return sumV
# def canPartition(link,sumV,m):
#     if sumV % m != 0:
#         return False
#     subSum = sumV / m
#     if subSum < link[0]:
#         return False
#     while len(link) > 0 and link[0] == subSum:
#         link.pop(0)
#         m -= 1
#     buckets = [0] * m
#     return partition(link,0,buckets,subSum)
# def partition(link,index,buckets,subSum):
#     if index == len(link):
#         return True
#     select = link[index]
#     for i in range(len(buckets)):
#         if i > 0 and buckets[i] == buckets[i-1]:
#             continue
#         if select + buckets[i] <= subSum:
#             buckets[i] += select
#             if partition(link,index+1,buckets,subSum):
#                 return True
#             buckets[i] -= select
#     return False
#
# print(getRes(link,m))

#93最大花费金额
# costs = list(map(int,input().split(',')))
# money = int(input())
# costs.sort()
# n = len(costs)
# sumv = 0
# for i in range(n):
#     l = i+1
#     r = n-1
#     while l < r:
#         cot = costs[i] + costs[l] + costs[r]
#         if cot == money:
#             print(cot)
#             exit(0)
#         elif cot < money:
#             sumv = max(cot,sumv)
#             l+=1
#         else:
#             r-=1
# print(sumv)

#94照明区间
# n = int(input())
# arr = list(map(int,input().split()))
#
# rans = []
# for i in range(n):
#     center = i * 100
#     rans.append([center - arr[i],center + arr[i]])
# rans.sort(key = lambda x:(x[0],-x[1]))
#
# ans = 0
# t = rans[0][1]
# for i in range(1,n):
#     s,e = rans[i]
#     if t >= s:
#         t = max(t,e)
#     else:
#         ans +=  s-t
#         t = e
# print(ans)

#95字符串重新排序
# words = input().split()
# for i in range(len(words)):
#     words[i] = ''.join(sorted(words[i]))
# print(words)
# num = {}
# length = {}
# for word in words:
#     # if length[word] is None:
#     #     length[word] = len(word)
#     num[word] = num.get(word,0)+1
#
# words.sort(key=lambda x:(-num[x],len(x),x))
# # print(words)
# print(' '.join(words))

#96计算最接近的数
# 输入获取
# tmp = input()
# i = tmp.rfind(",")
# x = list(map(int, tmp[1:i - 1].split(",")))
# k = int(tmp[i + 1:])
# # 核心代码
# def getResult():
#     n = len(x)
#     # x数组的中位数
#     mid = sorted(x)[n // 2]
#     # 初始化滑窗0~k-1, window为滑窗内部元素的表达式计算结果
#     window = x[0]
#     for j in range(1, k):
#         window -= x[j]
#     # window和中位数的差距
#     minDiff = abs(mid - window)
#     # window滑窗起始索引
#     idx = 0
#     # 滑窗右移
#     for i in range(1, n - k + 1):
#         # 右移一格后，新滑窗的表达式计算结果
#         window += -x[i - 1] + 2 * x[i] - x[i + k - 1]
#
#         # 新滑窗window值和中位数的差距
#         diff = abs(mid - window)
#
#         # 结果最接近于数组中位数的下标 i ，如果有多个 i 满足条件，请返回最大的 i
#         if diff <= minDiff:
#             minDiff = diff
#             idx = i
#     return idx

#97分奖金
# n = int(input())
# nums = list(map(int,input().split()))
# nextBiggerIndex = [-1] * n
# stack = []
# for i in range(n):
#     while stack and nums[i] > nums[stack[-1]]:
#         print(stack[-1])
#         nextBiggerIndex[stack.pop()] = i
#     stack.append(i)
#     print(stack)
# print(nextBiggerIndex)

#98ai面板识别
# class Light:
#     def __init__(self,id,x,y,r):
#         self.id = id
#         self.x = x
#         self.y = y
#         self.r = r
# n = int(input())
# arr = [list(map(int,input().split())) for _ in range(n)]
# lights = list(map(lambda ele: Light(ele[0], (ele[1] + ele[3]) // 2, (ele[2] + ele[4]) // 2, (ele[3] - ele[1]) // 2), arr))
# lights.sort(key = lambda l : l.y)
# ans = []
#
# sameRowLights = []
# base = lights[0]
# sameRowLights.append(base)
#
# for i in range(1,len(lights)):
#     light = lights[i]
#
#     if light.y - base.y <= base.r:
#         sameRowLights.append(light)
#     else:
#         sameRowLights.sort(key=lambda l:l.x)
#         for l in sameRowLights:
#             ans.append(l.id)
#         sameRowLights.clear()
#         base = light
#         sameRowLights.append(base)
#
# if len(sameRowLights) > 0:
#     sameRowLights.sort(key = lambda l : l.x)
#     for l in sameRowLights:
#         ans.append(l.id)
# print(' '.join(map(str,ans)))

#99静态代码扫描服务
# 输入获取
# m = int(input())
# f = list(map(int, input().split()))
# s = list(map(int, input().split()))
# # 核心代码
# def solution():
#     # count用于保存每个文件出现的次数
#     count = {}
#     # size用于保存文件的大小，即扫描成本
#     size = {}
#     for i in range(len(f)):
#         # k是文件标识
#         k = f[i]
#         count[k] = count.get(k, 0) + 1
#         if size.get(k) is None:
#             size[k] = s[i]
#     ans = 0
#     for k in count.keys():
#         # 选择每次都重新扫描的成本  和  扫描一次+缓存的成本  中最小的
#         ans += min(count[k] * size[k], size[k] + m)
#     return ans


#100最多可以派出几个团队
# num = int(input())
# arr = list(map(int,input().split()))
# print(arr)
# n = len(arr)
# arr.sort(reverse=True)
# ans = 0
# for i in range(n):
#     if arr[i] >= num:
#         ans+=1
#         arr.pop(0)
# print(arr)
# l = 0
# r = len(arr) - 1
# while l < r:
#     if arr[l] + arr[r] >= num:
#         ans+=1
#         l+=1
#         r-=1
#     else:
#         l+=1
# print(ans)

#101最大子矩阵和
# m,n = map(int,input().split())
# matrix = [list(map(int,input().split())) for _ in range(m)]
# def maxNum(arr):
#     dp = arr[0]
#     for i in range(1,n):
#         dp = max(dp,0) + arr[i]
#     return dp
# ans = -sys.maxsize
# for i in range(m):
#     ans = max(ans,maxNum(matrix[i]))
#     for j in range(i+1,m):
#         for k in range(n):
#             matrix[i][k] += matrix[j][k]
#         ans = max(ans,maxNum(matrix[i]))
# print(ans)

#102最短木板长度
# n,m = map(int,input().split())
# nums = list(map(int,input().split()))
# pq = []
# for c in nums:
#     heapq.heappush(pq,c)
# for i in range(m):
#     heapq.heappush(pq,heapq.heappop(pq)+1)
# print(heapq.heappop(pq))
# nums.sort()
# arr = nums
# dp = 0
# for i in range(1,n):
#     need = (arr[i] - arr[i-1]) * i
#     if dp + need > m:
#         print((m-dp) // i + arr[i-1])
#         break
#     dp += need
# print((m-dp)//n + arr[-1])

#103之字形
# arr = input().split()
# s = list(arr[0])
# n = int(arr[1])
# reverseFlag = False
# ans = [[] for _ in range(n)]
# for i in range(len(s)):
#     if i % n == 0:
#         reverseFlag = not reverseFlag
#     if reverseFlag:
#         ans[i%n].append(s[i])
#     else:
#        ans[n - 1 - i % n].append(s[i])
# for arr in ans:
#     print(''.join(arr))

#104最远足迹
# import re
# s = input()
# pattern = r"(^[1-9]\d+,^[1-9]\d+)"
# ret = re.findall(pattern,s)
#
# print(ret)
# n = len(ret)
# if n == 0:
#     print((0,0))
#     exit()
# ans = '(0,0)'
# dis = 0
# for i in range(n):
#     # arr = ret[i].split(',')
#     # print(arr)
#     x, y  = ret[i].split(',')
#     if x[0] == '0' or y[0] == '0':
#         continue
#     x= int(x)
#     y = int(y)
#     if x*x + y*y >= dis:
#         dis = x*x + y*y
#         ans = f'({x},{y})'
# print(ans)

#105堆内存申请
# ask = int(input())
# used = []
# for line in sys.stdin:
#     start,count = map(int,line.split())
#     used.append([start,start+count-1])
#
# def sol():
#     if ask <= 0 or ask > 100:
#         return -1
#     memory = [0] * 100
#     for s,e in used:
#         if s < 0 or s>= 100:
#             return -1
#         if e < 0 or e >= 100:
#             return -1
#         for i in range(s,e+1):
#             if memory[i] != 0:
#                 return -1
#             else:
#                 memory[i] = 1
#     ans = -1
#     min_size = sys.maxsize
#     l = 0
#     while l < 100:
#         while l < 100 and memory[l] != 0:
#             l+=1
#         if l>= 100:
#             break
#         r  = l + 1
#         while r < 100 and memory[r] == 0:
#             r += 1
#         free_size = r-l
#         if ask <= free_size < min_size:
#             min_size = free_size
#             ans = l
#         l = r+1
#
#     return ans

#106租车骑绿道
# 输入获取
# nums = eval(input())
# limit = int(input())
# # 算法入口
# def solution():
#     nums.sort()
#     count = 0
#     i = 0
#     j = len(nums) - 1
#
#     while i <= j:
#         if nums[i] + nums[j] <= limit:
#             i += 1
#         j -= 1
#         count += 1
#     return count


#107Ai处理器申请
# array = eval(input())
# num = int(input())
# array.sort()
# link1 = []
# link2 = []
# def dfs(link,level,index,path,res):
#     if len(path) == level:
#         res.append(path[:])
#         return
#     for i in range(index,len(link)):
#         path.append(link[i])
#         dfs(link,level,i+1,path,res)
#         path.pop()
# for i in array:
#     if i < 4:
#         link1.append(i)
#     else:
#         link2.append(i)
# res = []
# if num == 8:
#     if len(link1) == 4 and len(link2) == 4:
#         link1.extend(link2)
#         res.append(link1)
# else:
#     dic = {
#         1:[1,3,2,4],
#         2:[2,4,3],
#         4:[4]
#     }
#     for i in dic[num]:
#         if len(link1) == i or len(link2) == i:
#             if len(link1) == i:
#                 dfs(link1,num,0,[],res)
#             if len(link2) == i:
#                 dfs(link2,num,0,[],res)
#             break
# print(res)

#108寻找关键钥匙
# 输入解析
# key = input()
# boxes = input().split()
# def solution():
#     for i in range(len(boxes)):
#         # 箱子中字符串s
#         s = boxes[i]
#         # 只保留字符串s中的字母
#         letters = []
#         for c in s:
#             if 'z' >= c >= 'a':
#                 letters.append(c)
#             elif 'Z' >= c >= 'A':
#                 # 忽略字母大小写，这里只保留小写，遇到大写字母则转为小写字母
#                 letters.append(c.lower())
#
#         # 由于密码key是升序的不重复小写字母组成
#         # 因此对只有小写字母的letters升序和拼接，如果结果和key相同则找到了目标箱子
#         letters.sort()
#
#         if "".join(letters) == key:
#             # 由于题目提示：满足条件的箱子不超过1个，因此一旦找到，则可以返回
#             # 箱子编号从1开始
#             return i + 1
#     # 如不存在符合要求的密码箱，则返回 -1
#     return -1

#109最长的顺子
# 输入获取
# my = input().split("-")
# used = input().split("-")
#
# # 牌面值 映射为 count列表索引值
# mapToV = {
#     "3": 3,
#     "4": 4,
#     "5": 5,
#     "6": 6,
#     "7": 7,
#     "8": 8,
#     "9": 9,
#     "10": 10,
#     "J": 11,
#     "Q": 12,
#     "K": 13,
#     "A": 14,
#     "2": 16,
#     "B": 17,
#     "C": 18
# }
#
# # count列表索引值 隐射为 牌面值
# mapToK = {
#     3: "3",
#     4: "4",
#     5: "5",
#     6: "6",
#     7: "7",
#     8: "8",
#     9: "9",
#     10: "10",
#     11: "J",
#     12: "Q",
#     13: "K",
#     14: "A",
#     16: "2",
#     17: "B",
#     18: "C"
# }
# # 算法入口
# def getResult():
#     # count每个索引值对应一个牌面值，count元素值就是对应牌面的数量
#     # 牌面值           3  4  5  6  7  8  9  10 J  Q  K  A     2  B  C
#     # 索引值           3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18
#     count = [0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0, 4, 1, 1]
#
#     # 总牌数 减去 自己手中牌数
#     for k in my:
#         count[mapToV[k]] -= 1
#     # 总牌数 减去 已打出去的牌数
#     for k in used:
#         count[mapToV[k]] -= 1
#     # 最长连续牌的长度
#     maxLen = 0
#     # 最长连续牌的起始位置
#     maxL = -1
#     # 顺子范围是 3~A, 对应索引范围是 3 ~ 14
#     l = 3
#     r = 3
#     # 这里r探索到15，是因为15不是顺子有效范围，因此count[15]必然为0，可以作为收尾哨兵
#     while r <= 15:
#         if count[r] > 0:
#             # 如果对应牌数量>0，则可以维持连续
#             r += 1
#         else:
#             # 否则连续性打断，此时 [l, r) 左闭右开区间是连续牌
#             # 注意这里是>=而不是>，因为题目说如果遇到长度相同的顺子，则取较大牌面的。而后出现的顺子肯定牌面更大，因此后出现的相同的顺子更大。
#             if r - l >= maxLen:
#                 maxLen = r - l  # 记录更长的连续牌
#                 maxL = l
#             # l,r 移动到 r+1 位置
#             r += 1
#             l = r
#     #  如果最长连续牌长度不足5，那么就没有顺子
#     if maxLen < 5:
#         return "NO-CHAIN"
#     # 否则就有最长顺子
#     cards = []
#     for i in range(maxLen):
#         cards.append(mapToK[maxL + i])
#     return "-".join(cards)

#110获得完美走位
# if __name__ == '__main__':
#     s = input()
#
#     # 统计输入串中各个字母的出现次数
#     count = {}
#     for c in s:
#         count[c] = count.get(c, 0) + 1
#
#     # 字符串长度 / 字母种类数 = 平衡度k
#     k = len(s) // len(count.keys())
#
#     total = 0  # 总冗余度
#     for c in count:
#         count[c] = max(count[c] - k, 0)  # c 字符的冗余度，若 c 字符出现次数 x 超出 k，则冗余度为 x-k，否则冗余度为0
#         total += count[c]
#
#     if total == 0:
#         print("-1 0")
#         exit()
#
#     start = -1
#     minLen = float('inf')
#
#     # 尺取法，变种滑动窗口，滑窗范围 [l, r]
#     l, r = 0, 0
#     while r < len(s):
#         if count[s[r]] > 0:
#             total -= 1
#         count[s[r]] -= 1
#
#         while total == 0:
#             length = r - l + 1
#
#             if length < minLen:
#                 minLen = length
#                 start = l
#
#             if count[s[l]] >= 0:
#                 total += 1
#             count[s[l]] += 1
#             l += 1
#         r += 1
#     print(f"{start} {minLen}")


# 111字符串解密算法
# s1 = input()
# s2 = input()
# import re
# pattern = r'[0-9a-f]+'
# valids = re.split(pattern,s1)
# count = len(set(s2))
# ans = list(filter(lambda valid:valid != '' and len(set(valid))<=count,valids))
# print(ans)
# if len(ans) > 0:
#     ans.sort(key=lambda  x: (-len(set(x)),[-ord(char) for char in x]))
#     print(ans)
#     print(ans[0])
# else:
#     print("Not found")

#112寻找密码 最长密码算法
# s = input().split()
# s.sort(key= lambda x:(-len(x), [-ord(c) for c in x]))
# word = set(s)
# ans = ''
# for c in s:
#     string = c[:-1]
#     while len(string) > 0:
#         if string not in word:
#             break
#         string = string[:-1]
#     if len(string) == 0:
#         ans = c
#         break
# print(ans)

#113遍历完全二叉树非叶子结点
# def dfs(root):
#     left = root * 2 + 1
#     right = root * 2 + 2
#     if len(arr) > left:
#         dfs(left)
#         if len(arr) > right:
#             dfs(right)
#     non_leafs.append(arr[root])
#
# arr = input().split()
# if len(arr) == 1:
#     print(arr[0])
# else:
#     non_leafs = []
#     dfs(0)
#     print(' '.join(non_leafs))

#115精准核酸检测
# class UnionFindSet:
#     def __init__(self,n):
#         self.fa = [i for i in range(n)]
#     def find(self,x):
#         if x!= self.fa[x]:
#             self.fa[x] = self.find(self.fa[x])
#             return self.fa[x]
#         return x
#     def union(self,x,y):
#         x_fa = self.find(x)
#         y_fa = self.find(y)
#         if x_fa != y_fa:
#             self.fa[y_fa] = x_fa
#
# n = int(input())
# confirmed = list(map(int,input().split(',')))
# matrix = [list(map(int,input().split(","))) for _ in range(n)]
#
# ufs = UnionFindSet(n)
# for i in range(n):
#     for j in range(i,n):
#         if matrix[i][j] == 1:
#             ufs.union(i,j)
#
# cnts = [0] * n
# for i in range(n):
#     fa = ufs.find(i)
#     cnts[fa] += 1
#
# confirmed_fa = set()
# ans = 0
# for i in confirmed:
#     fa = ufs.find(i)
#
#     if fa in confirmed_fa:
#         continue
#     confirmed_fa.add(fa)
#
#     ans += cnts[fa]
#
# print(ans-len(confirmed))

#114 任务总执行时长
# 输入获取
# taskA, taskB, num = map(int, input().split(","))
#
# def solution():
#     if num == 0:
#         return "[]"
#
#     if taskA == taskB:
#         return [taskA * num]
#     ans = set()
#     for i in range(num + 1):
#         ans.add(taskA * i + taskB * (num - i))
#     return sorted(ans)

#116冠亚季军算法
# from collections import deque
# arr = list(map(int,input().split()))
# idx = [i for i in range(len(arr))]
# link = deque()
# link.appendleft(idx)
#
# while len(link[0]) > 1:
#     ids = link.popleft()
#     win = []
#     lose = []
#     for i in range(1,len(ids),2):
#         majorId = ids[i]
#         minorId = ids[i-1]
#         if arr[majorId] > arr[minorId]:
#             win.append(majorId)
#             lose.append(minorId)
#         else:
#             lose.append(majorId)
#             win.append(minorId)
#     if len(ids) % 2 != 0:
#         win.append(ids[-1])
#
#     link.appendleft(lose)
#     link.appendleft(win)
#
#     first = link[0][0]
#     second = link[1][0]
#     link[2].sort(key = lambda x:(-arr[x],x))
#     third = link[2][0]

#117 最多提取子串数目
# if __name__ == '__main__':
#     a = input()
#     b = input()
#     # indexes对象记录字符串b中每个字符的索引
#     indexes = {}
#     for i in range(len(b)):
#         indexes[b[i]] = i
#     # count对象用于记录遍历字符串a每个字符串过程中，统计到的符合顺序要求的字符串b中字符出现次数
#     count = [0] * len(b)
#     for c in a:
#         idx = indexes.get(c)
#         # 下面判断逻辑请看图解
#         if idx is not None and (idx == 0 or count[idx] < count[idx - 1]):
#             count[idx] += 1
#     print(count[-1])


#118最大括号深度括号匹配
# s = input()
# dic = {
#     ')':'(',
#     ']':'[',
#     '}':'{'
# }
# stack = []
# maxDepth = 0
# for c in s:
#     if len(stack) > 0 and c in dic and dic[c] == stack[-1]:
#         stack.pop()
#     else:
#         stack.append(c)
#         maxDepth = max(maxDepth,len(stack))
#
# if stack:
#     print(0)
# else:
#     print(maxDepth)

#119计算相对开音节子串
# s = input().split()
# # import re
# # pat = re.compile(r'[^a-z]')
# # pat1 = re.compile(r'[^aeiou][aeiou][^aeiour]]e')
# # pat2 = re.compile(r'e[^aeiour][aeiou][^aeiou]')
# # count = 0
# # for st in s:
# #     ret = pat1 if pat.search(st) else pat2
# #     # ret = pat2
# #     for i in range(len(st) - 3):
# #         res = st[i:i+4]
# #         if pat.search(res):
# #             continue
# #         if ret.match(res):
# #             count+=1
# # print(count)

#120太阳能板最大面积
# heights = list(map(int,input().split(',')))
# l = 0
# r = len(heights) - 1
# maxArea = 0
#
# while l < r:
#     x = r - l
#     y = 0
#     if heights[l] < heights[r]:
#         y = heights[l]
#         l+=1
#     else:
#         y = heights[r]
#         r -=1
#     maxArea = max(maxArea,x * y)

#121单词下表区间翻转文章
# s = input().split()
# start = int(input())
# end = int(input())
# start = min(max(start,0),len(s)-1)
# end = min(max(end,0),len(s)-1)
#
# while start < end:
#     s[start],s[end] = s[end],s[start]
#     start += 1
#     end -= 1
# print(' '.join(s))

#122事件推送
# m,n,r = map(int,input().split())
# a = list(map(int,input().split()))
# b = list(map(int,input().split()))
#
# i = j = 0
# while i < m and j < n:
#     if a[i] <= b[j]:
#         if a[i] - b[j] <= r:
#             print(f"{a[i]} {b[j]}")
#         i += 1
#     else:
#         j += 1

#123开心消消乐
# def bfs(i, j):
#     queue = [(i, j)]
#     matrix[i][j] = 0
#     while len(queue) > 0:
#         x, y = queue.pop(0)
#         for dx, dy in offsets:
#             newX = x + dx
#             newY = y + dy
#             if n > newX >= 0 and m > newY >= 0 and matrix[newX][newY] == 1:
#                 queue.append((newX, newY))
#                 matrix[newX][newY] = 0
#
# if __name__ == '__main__':
#     n, m = map(int, input().split())
#     matrix = [list(map(int, input().split())) for _ in range(n)]
#     # 八个方向的偏移量
#     offsets = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))
#     count = 0
#     for i in range(n):
#         for j in range(m):
#             if matrix[i][j] == 1:
#                 count += 1
#                 bfs(i, j)
#     print(count)


#124 模拟商场打折
# def M(p, m):
#     """
#     满减规则
#     :param p: 总价
#     :param m: 满减券数量
#     :return: 总价满减后结果，对应数组含义是 (用券后剩余总价， 剩余满减券数量)
#     """
#     while p >= 100 and m > 0:
#         p -= int(p / 100) * 10
#         m -= 1
#     return p, m
# def N(p, n):
#     """
#     打折规则
#     :param p: 总价
#     :param n: 打折券数量
#     :return: 总价打折后结果，对应数组含义是 (用券后剩余总价， 剩余打折券数量)
#     """
#     if n >= 1:
#         p = int(p * 0.92)
#         n -= 1
#     return p, n
# def K(p, k):
#     """
#     无门槛你规则
#     :param p: 总价
#     :param k: 无门槛券数量
#     :return: 门槛券用后结果，对应数组含义是 (用券后剩余总价， 剩余无门槛券数量)
#     """
#     while p > 0 and k > 0:
#         p -= 5
#         p = max(p, 0)  # 无门槛券过多会导致优惠后总价小于0，此时我们应该避免
#         k -= 1
#     return p, k
#
# if __name__ == '__main__':
#     m, n, k = map(int, input().split())
#     x = int(input())
#     for _ in range(x):
#         price = int(input())
#         ans = []
#         resM = M(price, m)  # 先满减
#         resMN_N = N(resM[0], n)  # 满减后打折
#         ans.append(
#             (resMN_N[0], m + n - (resM[1] + resMN_N[1])))  # m + n 是满减后打折方式的总券数量， resM[1] + resMN_N[1] 是满减券剩余数+打折券剩余数
#
#         resMK_K = K(resM[0], k)  # 满减后无门槛
#         ans.append((resMK_K[0], m + k - (resM[1] + resMK_K[1])))
#
#         resN = N(price, n)  # 先打折
#         resNM_M = M(resN[0], m)  # 打折后满减
#         ans.append((resNM_M[0], n + m - (resN[1] + resNM_M[1])))
#
#         resNK_K = K(resN[0], k)  # 打折后无门槛
#         ans.append((resNK_K[0], n + k - (resN[1] + resNK_K[1])))
#
#         # 对ans进行排序，排序规则是：优先按剩余总价升序，如果剩余总价相同，则再按“使用掉的券数量”升序
#         ans.sort(key=lambda lst: (lst[0], lst[1]))
#         print(" ".join(map(str, ans[0])))